1. Field of the Invention
The present invention is generally related to digital computers that utilize a memory stack and more particularly relates to means for checking the validity of the operation of the memory stack.
2. Description of the Prior Art
A key element in the design of high reliability computer systems is error detection. The term "error detection" refers to the detection of errors within a computer system before the errors adversely affect the arithmetic operations within the computer system. Many of today's computer systems incorporate some form of error detection to achieve improved reliability.
Large scale error detection has proved to be expensive to implement and maintain. In response thereto, many computer designers are limiting the use of error detection to portions of the computer system that can provide the most benefit. Memory elements are historically one place where error detection is targeted. Errors that occur either internal to a memory element or adjacent to the inputs or outputs of a memory element are far more likely to adversely affect the arithmetic operations within the computer system than those that occur in combinational logic. Memory elements must "store" data for later use whereas combinational logic merely operates on data in real time.
A specific type of memory element that is of interest is a memory stack. A memory stack contains a number of memory locations wherein each memory location may be accessed via a number of address busses. The address busses are typically called pointers. A typical memory stack may contain a read pointer and a write pointer for reading and writing data to the memory stack. In a typical system, a memory controller may cause one or more data words to be written into a series of address locations using the write pointer. At a later time, the memory controller may cause the previously written data elements to be read from the memory stack using the read pointer.
In one type of memory stack, called a first-in-first-out (FIFO) stack, the write pointer is incremented as data is written into the stack. Similarly, when reading data from the stack, the read pointer is incremented through the same memory locations as the write pointer passed through and in the same order, thus causing the first data element that is written to the FIFO stack to also be the first element that is read from the FIFO stack.
The absolute address location that is written or read via the write and read pointers is not important in a FIFO stack configuration. Rather, the relative difference between the write pointer and the read pointer is what defines valid data. The write and read pointers are typically generated by counters whereby the counters have a predetermined width. The width of the counters may be selected such that the counters have the same number of states as the corresponding response stack. In this way, the counters can be incremented such that the pointer address travels from a zero address to the maximum address of the memory element and then back to the zero address.
Memory stack elements are commonly used throughout modern day computer systems. One common application for a memory stack is to buffer data between two asynchronous devices. For example, a first device may write data into a memory stack even though the second device may not be prepared to read the data. Similarly, the second device may read the previously written data from the memory stack even though the first device may not be prepared to write data. Used in this manner, data may be transferred from a first asynchronously timed device to a second asynchronously timed device.
Several problems may occur in the operation of a memory stack which may cause unwanted errors within a high reliability computer system. Problems of data integrity within the memory stack itself can usually be handled using conventional redundancy or parity techniques. However, these techniques may not be very effective when dealing with functional problems such as improper read and write pointer operation. That is, parity and redundancy may rarely be used to detect the class of errors resulting from a memory controller improperly incrementing a read pointer to a location within the memory stack that has not yet been written using a write pointer. These problems stem primarily from the improper management of the read and write pointers of the memory stack.
In addition to the problems discussed above, several other problems may result from the improper management of the read and write pointers of a memory stack. First, the write pointer may be incremented to a location that contains data which has not yet been read by the read pointer. This may cause previously written data to be lost. Second, the read pointer may be incremented to a location which has not yet been written by the write pointer. This may cause invalid data to be propagated into the computer system. Third, the read pointer and the write pointer may attempt to simultaneously read and write a single address within the memory stack. This may cause invalid data to be read from or written to the specified address location within the memory stack.
Although the problems discussed above can be serious in a system having a common memory controller, the problems may be exacerbated when the read pointer and the write pointer are not controlled by a common memory controller. In some systems, the read pointer may be controlled by a first memory controller and the write pointer may be controlled by a second memory controller. The first memory controller and the second memory controller may be asynchronous relative to one another and may not communicate with one another with respect to valid read and write operations.
A consequence of having these problems within a high reliability computer system can be problematic. As stated above, convention error detection and correction techniques have proved to be inadequate. Prior attempts to manage the read and write pointers in an attempt to avoid these problems have primarily focused on software based solutions. Software based solutions are complex and require a significant amount of memory and processing power within the memory controllers. In addition, software based solutions can slow down system performance by requiring validity checks between each read or write operation.